//package student.duing.wangli;
//
//import com.duing.tree.plus.TreeNode;
//
//import java.util.*;
//
///**
// * 之字形 从上到下 打印二叉树
// */
//public class LevelOrder3 {
//    public static void main(String[] args) {
//        Integer[] arr = new Integer[]{3, 9, 20, 15, 7};
//        TreeNode node = CreateTree.createByArray(arr, 0);
//        List<List<Integer>> result = levelOrder(node);
//        System.out.println(result.toString());
//    }
//
//    /**
//     * 思路：基于levelOrder2 保证奇数层的节点值 按正常顺序打印
//     * 偶数层的节点值  倒序打印
//     */
//    public static List<List<Integer>> levelOrder(TreeNode root) {
//        List<List<Integer>> result = new ArrayList<>();
//        //使用双端队列 用来临时存储 每一层的  节点
//        Deque<TreeNode> deque = new LinkedList<>();
//        deque.offer(root);
//        //声明层数
//        int levelNum = 1;
//        while (deque.size() > 0) {
//            //处理 每一层的  节点
//            int n = deque.size();
//            //小集合
//            List<Integer> level = new ArrayList<>();
//            //层数加一
//            levelNum++;
//            for (int i = 0; i < n; i++) {
//                //将节点 出队
//                TreeNode node = deque.poll();
//                level.add(node.val);
//                //如果 当前节点 还有 左孩子或右孩子 入队
//                //入队之前 判断 是奇数层 还是偶数层
//                if (node.left != null) {
//                    if (levelNum % 2 == 0) {
//                        //偶数层
//                        deque.offerFirst(node.left);
//                    }else{
//                        deque.offer(node.left);
//                    }
//                }
//                if (node.right != null) {
//                    if (levelNum % 2 == 0) {
//                        deque.offerFirst(node.right);
//                    }else{
//                        deque.offer(node.right);
//                    }
//                }
//            }
//            result.add(level);
//        }
//        return result;
//    }
//
//
//}
